Codd's cellular automaton is a cellular automaton (CA) devised by the British computer scientist Edgar F. Codd in 1968. It was designed to recreate the computation- and construction-universality of von Neumann's CA but with fewer states: 8 instead of 29. Codd showed that it was possible to make a self-reproducing machine in his CA, in a similar way to von Neumann's universal constructor but never gave a complete implementation.
Contents |
In the 1940s and 50's, John von Neumann posed the following problem[1]:
He was able to construct a Universal Constructor with a square grid and 29 states. E.F. Codd found a simpler machine with only eight states[2]. Therefore von Neumann's question had to be modified:
Three years after Codd's work, Edwin Roger Banks showed a 4-state CA (appendix IV in his thesis) that was also computation- and construction-universal but again didn't implement a self-reproducing machine[3].
John Devore, in his 1973 master's thesis, was able to greatly reduce the size of Codd's machine design while using almost the same 8-state CA. More than just a theoretical device, Devore's machine was possibly the first implementation of a self-reproducing CA. The machine itself could fit inside computer memory but the data tape stretched for thousands of cells, so simulation of the entire self-reproduction cycle was not possible. Decades later, Devore's original design would complete self-reproduction in simulation using the Golly program.
In 1984, Christopher Langton extended Codd's cellular automaton to create Langton's loops[4], which also exhibits reproductive behavior but uses only a very small number of cells compared to the hundreds of thousands needed for self-reproduction in von Neumann, Codd or Banks' cellular automata.
| CA | number of states | symmetries | computation- and construction-universal | size of self-reproducing machine |
|---|---|---|---|---|
| von Neumann | 29 | none | yes | 130,622 cells |
| Codd | 8 | rotations | yes | 283,126,588 cells[5] |
| Devore | 8 | rotations | yes | 94,794 cells |
| Banks-IV | 4 | rotations and reflections | yes | unknown |
| Langton's loops | 8 | rotations | no | 86 cells |
Codd's CA has 8-states and the von Neumann neighborhood with rotational symmetry.
The table below shows the signal-trains needed to accomplish different tasks. Some of the signal trains need to be separated by two blanks (state 1) on the wire to avoid interference, so the 'extend' signal-train used in the image at the top appears here as '70116011'.
| purpose | signal train |
|---|---|
| extend | 70116011 |
| extend_left | 4011401150116011 |
| extend_right | 5011501140116011 |
| retract | 4011501160116011 |
| retract_left | 5011601160116011 |
| retract_right | 4011601160116011 |
| mark | 701160114011501170116011 |
| erase | 601170114011501160116011 |
| sense | 70117011 |
| cap | 40116011 |
| inject_sheath | 701150116011 |
| inject_trigger | 60117011701160116011 |
Codd designed a self-replicating computer in the cellular automaton, based on Wang's W-machine. However, the design was so colossal that it evaded implementation until 2009, when Tim Hutton constructed an explicit configuration[5]. There were some minor errors in Codd's design, so Hutton's implementation differs slightly, in both the configuration and the ruleset.